In computer architecture, instruction prefetching is a technique used to speed up the execution of a program by reducing wait states. Prefetching generally occurs when a processor or a sub-unit of a processor (e.g., a pre-fetch unit) requests an instruction or data block from a main memory before it is actually needed. Once the instruction/data block comes back from the main or system memory, the instruction/data block is typically placed in a cache. When a request is made to access the instruction/data block from the cache, the instruction/data block can be accessed much more quickly from the cache than if a request had to be made from the main or system memory. Thus, prefetching hides memory access latency.
Since programs are generally executed sequentially, performance is likely to be best when instructions are pre-fetched in program order. Alternatively, the pre-fetch may be part of a complex branch prediction algorithm, where the processor tries to anticipate the result of a calculation and fetch the right instructions in advance.
In computer architecture, a branch predictor or branch prediction unit is a digital circuit that attempts to guess which way a branch (e.g. an if-then-else structure, a jump instruction) will go before the result is actually computed and known. The purpose of the branch predictor is generally to improve the flow in the instruction pipeline. Branch predictors play a critical role in achieving high effective performance in many modern pipelined microprocessor architectures.
Two-way branching is usually implemented with a conditional jump instruction. A conditional jump can either be “not taken” and continue execution with the first branch of code which follows immediately after the conditional jump, or it can be “taken” and jump to a different place in program memory where the second branch of code is stored. It is often not known for certain whether a conditional jump will be taken or not taken until the condition has been calculated and the conditional jump has passed the execution stage in the instruction pipeline.
Without branch prediction, the processor typically would have to wait until the conditional jump instruction has passed the execute stage before the next instruction can enter the fetch stage in the pipeline. The branch predictor attempts to avoid this waste of time by trying to guess whether the conditional jump is most likely to be taken or not taken. The branch that is guessed to be the most likely is then fetched and speculatively executed. If the branch predictor detects that the guessed branch is wrong, the speculatively executed or partially executed instructions are often discarded and the pipeline starts over with the correct branch, incurring a delay.